// 支持动态增长的栈
typedef char STDataType;
typedef struct Stack
{
	STDataType* arr;
	int top;		 // 栈顶 (有效元素个数)
	int capacity;    // 容量 
}Stack;

void StackInit(Stack* ps)
{
	assert(ps);
	ps->capacity = 3;  //?
	ps->top = 0;
	ps->arr = (STDataType*)malloc(sizeof(STDataType)* ps->capacity);
	if (NULL == ps->arr){
		assert(0);     //申请空间失败断言
		return;
	}
}

// 销毁栈 
void StackDestroy(Stack* ps)
{
	assert(ps);
	if (ps->arr){    //栈 不为空
		free(ps->arr);
		ps->arr = NULL;
		ps->capacity = 0;
		ps->top = 0;
	}
}

//检查capacity,扩容
static void CheckCapacity(Stack* ps)
{
	//assert(ps);
	if (ps->top == ps->capacity){        //栈满
		int newcapacity = 2 * (ps->capacity);
		//1.开辟新空间
		STDataType* temp = (STDataType*)malloc(sizeof(STDataType) * newcapacity);
		if (NULL == temp){
			assert(0);
			return;
		}
		//2.拷贝元素
		//memcpy(temp, ps->arr, sizeof(STDataType)*ps->top);
        for (int i = 0; i < ps->top; ++i)
		{
			temp[i] = ps->arr[i];
		}
		//3.释放旧空间,使用新空间
		free(ps->arr);
		ps->arr = temp;
		ps->capacity = newcapacity;
	}
}


// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
int StackEmpty(Stack* ps)
{
	assert(ps);
	return 0 == ps->top;
}

// 入栈 
void StackPush(Stack* ps, STDataType data)
{
	assert(ps);
	CheckCapacity(ps);
	ps->arr[ps->top] = data;
	(ps->top)++;
}

// 出栈 
void StackPop(Stack* ps)
{
	assert(ps);
	if (!StackEmpty(ps)){      //栈不为空
		ps->top--;
	}
}

// 获取栈顶元素 
STDataType StackTop(Stack* ps)
{
	assert(!StackEmpty(ps));     //栈不为空，才有栈顶元素，为空则触发断言
    return ps->arr[ps->top - 1];

}

//判断括号是左括号还是右括号
int Check(char s)
{
    if(s == '(' || s == '{' || s=='['){
        return 1;
    }
    else if(s == ')' || s == '}' || s==']'){
        return 2;
    }
    return 0;
}

//如果是左括号将其转换为对应的右括号返回
int CheckRight(char s)
{
    if(s == '('){
        return ')';
    }
    if(s == '{'){
        return '}';
    }
    if(s == '['){
        return ']';
    }
    return 0;
}

bool isValid(char * s){
    int size = strlen(s);
    if(size & 1 || Check(*s) == 2){          //如果字符串长度为奇数一定不有效
        return false;
    }
    Stack s1;
    StackInit(&s1);       //初始化栈 
    bool flag = false;
    for(int i = 0;i < size;i++){
        if(Check(s[i]) == 1){     //如果是左括号入栈
            StackPush(&s1,s[i]);
        }
        else {             //如果是右括号
            if(StackEmpty(&s1)){   //栈中没有左括号匹配时不满足，退出
                StackDestroy(&s1);
                return false;
            }
            char ch = StackTop(&s1);
            if(CheckRight(ch) == s[i]){    
                 StackPop(&s1);           //栈中左括号和s[i]匹配，左括号出栈
            }
            else{
                break;
            }
                //说明条件满足，左括号出栈继续循环
        }
        
    }
    if(StackEmpty(&s1)){    //栈空(没有左括号)说明匹配完成
        flag = true;
    }
    StackDestroy(&s1);     //释放开辟的栈空间
    return flag;
}

